package org.syntaxlisp.core.match.tree;

import org.syntaxlisp.core.ParseException;
import org.syntaxlisp.core.PreMatchingProcess;
import lombok.Builder;
import lombok.Getter;
import lombok.Setter;
import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.lang3.StringUtils;
import org.syntaxlisp.core.element.*;
import org.syntaxlisp.core.match.*;
import org.syntaxlisp.core.utils.*;

import java.io.FileNotFoundException;
import java.util.*;
import java.util.stream.Collectors;

import static org.syntaxlisp.core.utils.CommonUtils.*;

public class PureCursorMatcher implements Matcher {

    private final Map<DefID, MatchState> entryMap;

    private final Map<DefID, SyntaxLispElement> env;

    private final Map<DefID, Set<DefID>> firstRefReduceMap;

    private final Map<DefID, Set<DefID>> reduceToFirstRefMap;

    private final Map<DefID, Set<DefID>> directFirstRefReduceMap;

    private final Map<DefID, Set<DefID>> directReduceToFirstRefMap;

    private boolean enableHungerReduceDefMode;

    private boolean enableErrorCollectMode;

    private boolean hasMatchedStartAtCurInputOffset = false;

    private boolean enableLongestMatch;

    /**
     * 是否打开打印 reduce trace
     */
    private boolean enablePrintReduceTrace;

    /**
     * 是否使用预匹配模式
     */
    private boolean enablePredicateMap;

    private boolean reachMatchEnd = false;

    Map<DefID, MatchState> stateEnv;

    Map<SyntaxLispElement, MatchState> elementStateMap;

    /**
     * 生成 firstRefStateMap
     */
    Map<DefID, Map<DefID, Set<MatchState>>> firstRefStatesMap;

    /**
     *
     */
    Map<DefID, Map<DefID, Set<MatchState>>> reduceAsFirstRefStatesMap;

    private Map<DefID, Map<DefID, Set<DefID>>> firstRefReduceMidSetMap;

    private Map<DefID, Map<DefID, Set<DefID>>> firstRefReduceDirectToMap;


    // 以下为新版本 TreeMatcher 状态 Map
    /**
     * (start, end) -> trail List (trail 直接使用 MatchSeqNode)
     */
    Map<Integer, Map<Integer, List<TrailUnit>>> trailMap;

    Map<Integer, Set<Integer>> trailWithEndMap;

    /**
     * def -> start -> end -> match seq node
     */
    Map<DefID, Map<Integer, Map<Integer, NewMatchSeqNode>>> defMatchResMap;


    PureCursorProvider cursorProvider;

    Set<DefID> canReduceToEntryAsFirstRefSet;

    List<MatchUnit> inputSeq;

    Map<DefID, Map<DefID, Set<MatchState>>> defDirectRefPfStatesMap;

    private PureCursor latestTryMatchCursor;

    private List<PureCursor> latestTryMatchCursorList;

    private LambdaInteger cursorIdGenerator;

    private ListTree<RepeatFrame> repeatFrameListTree;

    private Map<String, DefID> defIdMap;

    private Collection<DefID> entryDefs;

    private AcceptSet possibleFirstAcSet;

    private AcceptSet pureContainsAcSet;

    private AcceptSet possibleEndSet;

    public PureCursorMatcher(String langPath,
                             Collection<String> entries,
                             boolean enableHungerReduceDefMode,
                             boolean enableErrorCollectMode,
                             boolean enableLongestMatch,
                             boolean enablePrintReduceTrace,
                             boolean enablePredicateMap) throws FileNotFoundException {

        this.enableHungerReduceDefMode = enableHungerReduceDefMode;
        this.enableErrorCollectMode = enableErrorCollectMode;
        this.enableLongestMatch = enableLongestMatch;
        this.enablePrintReduceTrace = enablePrintReduceTrace;
        this.enablePredicateMap = enablePredicateMap;

        checkOrThrow(!StringUtils.isBlank(langPath), "Lang path can not be blank!");
        checkOrThrow(!CollectionUtils.isEmpty(entries), "Entries can not be null!");

        Pair<Map<String, SyntaxLispElement>, Collection<String>> processRes
                = PreMatchingProcess.parseLangEnv(langPath, entries);

        Map<String, SyntaxLispElement> langEnv = processRes.getFirst();

        Collection<String> bases = processRes.getSecond();

        defIdMap = buildDefIdMap(langEnv.keySet(), bases);

        entryDefs = new HashSet<>(entries.size());
        entries.forEach(entry -> entryDefs.add(defIdMap.get(entry)));

        PreMatchingProcess.CriticalProcessingBeforeMatchRes first
                = PreMatchingProcess.criticalProcessingWithPriority(langEnv, defIdMap);

        PreMatchingProcess.CriticalProcessingBeforeMatchRes last
                = PreMatchingProcess.criticalProcessingBeforeMatch(langEnv, false,
                                                                   true, defIdMap);

        Map<DefID, Set<SyntaxLispElement>> purePossibleContains
                = PreMatchingProcess.determinePossibleContains(langEnv, defIdMap);

        new AcceptSet(first.getDefPfMap(), defIdMap);

        possibleFirstAcSet = new AcceptSet(first.getDefPfMap(), defIdMap);
        pureContainsAcSet = new AcceptSet(purePossibleContains, defIdMap);
        possibleEndSet = new AcceptSet(last.getDefPfMap(), defIdMap);


        firstRefReduceMap = first.getFirstRefReduceMap();
        reduceToFirstRefMap = first.getReduceToFirstRefMap();

        firstRefReduceMidSetMap = first.getFirstRefReduceMidSetMap();
        firstRefReduceDirectToMap = first.getFirstRefReduceDirectToMap();

        directFirstRefReduceMap = new HashMap<>(langEnv.size());
        directReduceToFirstRefMap = new HashMap<>(langEnv.size());

        cursorProvider = new PureCursorProvider();

        repeatFrameListTree = new ListTree<>(RepeatFrame::getHashKey);

        langEnv.forEach((curDef, body) -> {
            DefID curDefID = defIdMap.get(curDef);
            Set<DefID> directPfRefSet = new HashSet<>();
            body.getDirectPf().forEach(pf -> {
                if (SyntaxLispElementType.REF == pf.getType()) {
                    DefID pfID = defIdMap.get(pf.getVal());
                    directPfRefSet.add(pfID);
                    directReduceToFirstRefMap.computeIfAbsent(pfID, d -> new HashSet<>())
                                             .add(curDefID);
                }
            });
            directFirstRefReduceMap.put(curDefID, directPfRefSet);
        });

        env = new HashMap<>(langEnv.size());
        langEnv.forEach((def, body) -> env.put(defIdMap.get(def), body));


        trailMap = new HashMap<>();
        trailWithEndMap = new HashMap<>();

        initTreeState();
        entryMap = new HashMap<>(entries.size());
        entryDefs.forEach(entry -> entryMap.put(entry,
                                                Optional.ofNullable(stateEnv.get(entry))
                                                      .orElseThrow(() -> new RuntimeException("不存在的 Entry:"
                                                                                                      + entry))));
        canReduceToEntryAsFirstRefSet = new HashSet<>();
        entryDefs.forEach(entryDef -> {
            canReduceToEntryAsFirstRefSet.add(entryDef);
            canReduceToEntryAsFirstRefSet.addAll(firstRefReduceMap.getOrDefault(entryDef, Collections.emptySet()));
        });

        firstRefStatesMap = new HashMap<>();
        reduceAsFirstRefStatesMap = new HashMap<>();
        defDirectRefPfStatesMap = new HashMap<>();
        env.forEach((defID, body) -> {
            if (!CollectionUtils.isEmpty(body.getDirectPriorityPfList())) {

                Map<DefID, Set<MatchState>> curDirectRefPfStatesMap
                        = defDirectRefPfStatesMap.computeIfAbsent(defID, defName -> new HashMap<>());

                body.getDirectPriorityPfList().forEach(curPriorityDpfList -> {
                    Map<DefID, Set<MatchState>> curDirectRefPfStates = new HashMap<>();
                    curPriorityDpfList.forEach(dpf -> {
                        MatchState dpfState = elementStateMap.get(dpf);
                        DefID dpfID = dpfState.getDefID();
                        if (dpfState.isRef()
                                && !curDirectRefPfStatesMap.containsKey(dpfID)) {
                            curDirectRefPfStates.computeIfAbsent(dpfID, defName -> new HashSet<>())
                                                .add(dpfState);
                            reduceAsFirstRefStatesMap.computeIfAbsent(dpfID, defName -> new HashMap<>())
                                                     .computeIfAbsent(defID, curDef -> new HashSet<>())
                                                     .add(dpfState);
                        }
                    });
                    curDirectRefPfStatesMap.putAll(curDirectRefPfStates);
                });

                firstRefStatesMap.put(defID, curDirectRefPfStatesMap);
            }
        });

        // 构建 next state 到 direct next 映射 以及 state 的 hunger next states
        stateEnv.forEach((def, defState) -> initBaseNextToDirectNextMap(defState));

        defMatchResMap = new HashMap<>();

        cursorIdGenerator = new LambdaInteger(1);
    }

    private static Map<DefID, Set<DefID>> parseDefIDSetMap(Map<String, Set<String>> src, Map<String, DefID> defIdMap) {
        return src.entrySet()
                  .stream()
                  .map(entry -> Pair.<DefID, Set<DefID>>builder()
                          .first(defIdMap.get(entry.getKey()))
                          .second(parseDefIDSet(entry.getValue(), defIdMap))
                          .build())
                  .collect(Collectors.toMap(Pair::getFirst, Pair::getSecond));
    }

    private static Set<DefID> parseDefIDSet (Set<String> defSet, Map<String, DefID> defIdMap) {
        return defSet.stream().map(defIdMap::get).collect(Collectors.toSet());
    }

    private static Map<String, DefID> buildDefIdMap (Collection<String> defNames, Collection<String> bases) {
        int idCursor = 1;
        Map<String, DefID> defIDMap = new HashMap<>(defNames.size() + bases.size());
        for (String def : defNames) {
            defIDMap.put(def, DefID.builder().id(++ idCursor).def(def).build());
        }
        for (String base : bases) {
            defIDMap.put(base, DefID.builder().id(++ idCursor).def(base).build());
        }
        return defIDMap;
    }

    private static Map<Integer, Set<DefID>> buildPredicateMatchMap (List<MatchUnit> inputSeq,
                                                                    AcceptSet possibleFirst,
                                                                    AcceptSet purePossibleContains,
                                                                    AcceptSet possibleEnd) {

        Map<Integer, Set<DefID>> res = new HashMap<>(inputSeq.size());

        // next -> def -> start-end -> start scope
        TreeMap<Integer, Map<DefID, TreeMap<Integer, Scope>>> temp = new TreeMap<>();

        for (int i = 0; i < inputSeq.size(); i ++) {
            Map<DefID, Set<Integer>> endAcceptRes = possibleEnd.acceptToDefMap(inputSeq, i);
            Map<Integer, Set<DefID>> firstAcceptRes = possibleFirst.accept(inputSeq, i);

            // 匹配 pf
            int finalI = i;
            firstAcceptRes.forEach((next, defSet) -> {
                Map<DefID, TreeMap<Integer, Scope>> defScopeMap = temp.get(next);
                for (DefID curDef : defSet) {
                    if (defScopeMap != null) {
                        TreeMap<Integer, Scope> curDefScopeMap = defScopeMap.get(curDef);
                        if (curDefScopeMap != null) {
                            Scope scopeCanBeConnected = curDefScopeMap.remove(finalI - 1);
                            if (scopeCanBeConnected != null) {
                                scopeCanBeConnected.setEnd(finalI);
                            } else {
                                scopeCanBeConnected = Scope.builder().start(finalI).end(finalI).build();
                            }
                            if (endAcceptRes.containsKey(curDef)) {
                                setRes(curDef, scopeCanBeConnected, res);
                            } else {
                                curDefScopeMap.put(finalI, scopeCanBeConnected);
                            }
                        } else {
                            Scope scopeCanBeConnected = Scope.builder().start(finalI).end(finalI).build();
                            if (endAcceptRes.containsKey(curDef)) {
                                setRes(curDef, scopeCanBeConnected, res);
                            } else {
                                curDefScopeMap = new TreeMap<>();
                                curDefScopeMap.put(finalI, scopeCanBeConnected);
                                defScopeMap.put(curDef, curDefScopeMap);
                            }
                        }
                    } else {
                        Scope scopeCanBeConnected = Scope.builder().start(finalI).end(finalI).build();
                        if (endAcceptRes.containsKey(curDef)) {
                            setRes(curDef, scopeCanBeConnected, res);
                        } else {
                            TreeMap<Integer, Scope> curDefScopeMap = new TreeMap<>();
                            curDefScopeMap.put(finalI, scopeCanBeConnected);
                            defScopeMap = new HashMap<>();
                            defScopeMap.put(curDef, curDefScopeMap);
                            temp.put(next, defScopeMap);
                        }
                    }
                }
            });
            // 匹配 end 以及 pure contain
            Map<DefID, TreeMap<Integer, Scope>> removedDefScopeMap = temp.remove(i);
            if (removedDefScopeMap != null) {

                endAcceptRes.forEach(((defID, next) -> {
                    // 存在 end 的所有 def 进行入库
                    Map<Integer, Scope> acceptDefMap = removedDefScopeMap.remove(defID);
                    if (acceptDefMap != null) {
                        acceptDefMap.values().forEach(scope -> setRes(defID, scope, res));
                    }
                }));

                // 不存在 end 的 def，校验当前位置是否是 pure contain，
                // 则根据 pure contain 计算新的 next 并进入 temp 对应区域进行 scope 合并
                if (!removedDefScopeMap.isEmpty()) {
                    Map<DefID, Set<Integer>> pureContainAcRes = purePossibleContains.acceptToDefMap(inputSeq, i);
                    Collection<DefID> continueDefSet
                            = CollectionUtils.intersection(removedDefScopeMap.keySet(), pureContainAcRes.keySet());
                    continueDefSet.forEach(continueDef -> {
                        TreeMap<Integer, Scope> addedDefScopeMap = removedDefScopeMap.remove(continueDef);
                        pureContainAcRes.get(continueDef).forEach(next -> {

                            Map<DefID, TreeMap<Integer, Scope>> defScopeMap = temp.get(next);

                            if (defScopeMap != null) {
                                // 合并 Scope
                                TreeMap<Integer, Scope> curDefScopeMap = defScopeMap.get(continueDef);

                                if (curDefScopeMap != null) {
                                    for (Scope addScope : addedDefScopeMap.values()) {
                                        Map.Entry<Integer, Scope> startEntry
                                                = curDefScopeMap.ceilingEntry(addScope.getStart());
                                        if (startEntry != null) {
                                            Scope curAddScope = curDefScopeMap.remove(startEntry.getKey());
                                            addScope.setStart(Math.min(addScope.getStart(), curAddScope.getStart()));
                                            addScope.setEnd(Math.max(addScope.getEnd(), curAddScope.getEnd()));
                                        }
                                        Map.Entry<Integer, Scope> endEntry;
                                        while ((endEntry = curDefScopeMap.ceilingEntry(addScope.getEnd())) != null) {
                                            if (endEntry.getValue().getStart() <= addScope.getEnd()) {
                                                Scope curAddScope = curDefScopeMap.remove(endEntry.getKey());
                                                addScope.setStart(Math.min(addScope.getStart(),
                                                                           curAddScope.getStart()));
                                                addScope.setEnd(Math.max(addScope.getEnd(), curAddScope.getEnd()));
                                            } else {
                                                break;
                                            }
                                        }
                                        curDefScopeMap.put(addScope.getEnd(), addScope);
                                    }
                                } else {
                                    curDefScopeMap = new TreeMap<>(addedDefScopeMap);
                                    defScopeMap.put(continueDef, curDefScopeMap);
                                }
                            } else {
                                defScopeMap = new HashMap<>();
                                defScopeMap.put(continueDef, addedDefScopeMap);
                                temp.put(next, defScopeMap);
                            }
                        });
                    });
                }
            }
        }
        return res;
    }


    private static void setRes (DefID def, Scope acScope, Map<Integer, Set<DefID>> res) {
        for (int i = acScope.getStart(); i <= acScope.getEnd(); i ++) {
            res.computeIfAbsent(i, pos -> new HashSet<>()).add(def);
        }
    }

    @Builder
    @Getter
    @Setter
    private static class Scope {

        int start;

        int end;

        public int hashCode () {
            return end;
        }
    }

    private static class AcceptSet {

        HashMap<Character, Set<DefID>> characterDefMap;

        HashMap<DefID, Set<DefID>> baseDefMap;

        StringTreeMap<Set<DefID>> stringDefMap;

        public AcceptSet (Map<DefID, Set<SyntaxLispElement>> srcMap, Map<String, DefID> defIDMap) {
            characterDefMap = new HashMap<>();
            stringDefMap = new StringTreeMap<>();
            baseDefMap = new HashMap<>();
            srcMap.forEach((curDefID, srcSet) -> {
                for (SyntaxLispElement matchElement : srcSet) {
                    switch (matchElement.getType()) {
                        case BASE: {
                            baseDefMap.computeIfAbsent(defIDMap.get(matchElement.getVal()), d -> new HashSet<>())
                                      .add(curDefID);
                            break;
                        }
                        case CHARACTER: {
                            characterDefMap.computeIfAbsent(((CharacterElement) matchElement).getCharVal(),
                                                            d -> new HashSet<>())
                                           .add(curDefID);
                            break;
                        }
                        case SCOPE: {
                            for (Integer codepoint : ((MapScopeElement) matchElement).getAllCodepointInScope()) {
                                characterDefMap.computeIfAbsent((char) codepoint.intValue(), d -> new HashSet<>())
                                               .add(curDefID);
                            }
                            break;
                        }
                        case STRING: {
                            if (!stringDefMap.containsKey(matchElement.getVal())) {
                                stringDefMap.put(matchElement.getVal(), new HashSet<>());
                            }
                            stringDefMap.get(matchElement.getVal()).add(curDefID);
                            break;
                        }
                        default: {
                            throw new ParseException("Un-support element type in TreeState initMap operation.");
                        }
                    }
                }
            });
        }

        public Map<Integer, Set<DefID>> accept (List<MatchUnit> inputSeq, int offset) {
            Map<Integer, Set<DefID>> res = new HashMap<>();
            MatchUnit cur = inputSeq.get(offset);
            if (MatchUnitType.BASE == inputSeq.get(offset).getType()) {
                Set<DefID> baseMatchSet = baseDefMap.get(cur.getBaseId());
                if (baseMatchSet != null) {
                    res.put(1, baseDefMap.get(cur.getBaseId()));
                }

            } else {
                String val = (String) cur.getVal();
                if (val.length() == 1) {
                    Set<DefID> matchDefs = characterDefMap.get(val.charAt(0));
                    if (matchDefs != null) {
                        res.put(1, matchDefs);
                    }
                }
                List<Pair<Set<DefID>, Integer>> stringMatchRes = stringDefMap.match(inputSeq, offset);
                if (!CollectionUtils.isEmpty(stringMatchRes)) {
                    for (Pair<Set<DefID>, Integer> smr : stringMatchRes) {
                        res.computeIfAbsent(smr.getSecond(), n -> new HashSet<>())
                           .addAll(smr.getFirst());
                    }
                }
            }
            return res;
        }

        public Map<DefID, Set<Integer>> acceptToDefMap (List<MatchUnit> inputSeq, int offset) {
            Map<DefID, Set<Integer>> res = new HashMap<>();
            MatchUnit cur = inputSeq.get(offset);
            if (MatchUnitType.BASE == inputSeq.get(offset).getType()) {
                Set<DefID> baseMatchSet = baseDefMap.get(cur.getBaseId());
                if (baseMatchSet != null) {
                    baseMatchSet.forEach(defId -> res.put(defId, new HashSet<>(Collections.singleton(offset + 1))));
                }
            } else {
                String val = (String) cur.getVal();
                if (val.length() == 1) {
                    Set<DefID> matchDefs = characterDefMap.get(val.charAt(0));
                    if (matchDefs != null) {
                        matchDefs.forEach(defId -> res.put(defId, new HashSet<>(Collections.singleton(offset + 1))));
                    }
                }
                List<Pair<Set<DefID>, Integer>> stringMatchRes = stringDefMap.match(inputSeq, offset);
                if (!CollectionUtils.isEmpty(stringMatchRes)) {
                    for (Pair<Set<DefID>, Integer> smr : stringMatchRes) {
                        Set<DefID> matchDefSet = smr.getFirst();
                        for (DefID matchDef : matchDefSet) {
                            Set<Integer> defMatchOffsetSet = res.computeIfAbsent(matchDef, d -> new HashSet<>());
                            defMatchOffsetSet.add(smr.getSecond());
                        }
                    }
                }
            }
            return res;
        }

        @Builder
        @Getter
        public static class AcceptRes {

            private Set<DefID> defSet;

            private int acceptLength;

        }

    }

    private void initBaseNextToDirectNextMap (MatchState cur) {
        if (SyntaxLispElementType.SEQ_CONNECT == cur.getElementType()) {
            List<SyntaxLispElement> subs = cur.getSrc().getSubElements();
            subs.forEach(sub -> {
                MatchState subState = elementStateMap.get(sub);
                subState.setBaseNextBelongsToDirectNextMap(new HashMap<>());
                sub.getDirectNext().forEach(dn -> {

                    MatchState dnState = elementStateMap.get(dn);

                    setDirectNextAndNextMap(subState, dnState, subState.getNextBaseJumpMap(),
                                            dnState.getPfBaseJumpMap());

                    setDirectNextAndNextMap(subState, dnState, subState.getNextStringJumpMap(),
                                            dnState.getPfStringJumpMap());

                    setDirectNextAndNextMap(subState, dnState, subState.getNextCharacterJumpMap(),
                                            dnState.getPfCharacterJumpMap());
                });
            });
        }
        if (!CollectionUtils.isEmpty(cur.getSrc().getSubElements())) {
            cur.getSrc()
               .getSubElements()
               .forEach(sub -> initBaseNextToDirectNextMap(elementStateMap.get(sub)));
        }
    }

    private <K> void setDirectNextAndNextMap(MatchState cur,
                                             MatchState directNext,
                                             Map<K, Map<MatchState, Set<MatchState>>> nextJumpMap,
                                             Map<K, Map<MatchState, Set<MatchState>>> nextPfMap) {

        Collection<K> keys = CollectionUtils.intersection(nextPfMap.keySet(), nextJumpMap.keySet());
        keys.forEach(key -> {
            Collection<MatchState> sameBaseStates = CollectionUtils.intersection(nextPfMap.get(key).keySet(),
                                                                                 nextJumpMap.get(key).keySet());
            sameBaseStates.forEach(sameState -> {
                cur.getBaseNextBelongsToDirectNextMap().put(sameState, directNext);
                if (directNext.isHunger()) {
                    cur.getHungerStateSet().add(sameState);
                }
            });
        });
    }

    private void initTreeState () {
        stateEnv = new HashMap<>(env.size());
        elementStateMap = new HashMap<>();
        env.forEach((def, body) -> stateEnv.put(def, initStateFromElement(body, def)));
        elementStateMap.forEach((element, state) -> state.initMap(elementStateMap, defIdMap));
    }

    private MatchState initStateFromElement(SyntaxLispElement curElement, DefID belongsTo) {
        MatchState state = KBeanUtils.copyPropertiesWithoutTargetInstance(curElement, MatchState.class);
        if (curElement.isBase() || curElement.isRef()) {
            state.setDefID(defIdMap.get(curElement.getVal()));
        }
        state.setBelongsToDef(belongsTo);
        state.setSrc(curElement);
        state.setUpper(curElement.getUpper() != null
                       ? elementStateMap.get(curElement.getUpper())
                       : null);
        elementStateMap.put(curElement, state);
        if (SyntaxLispElementType.isNoTerminalType(curElement)) {
            for (SyntaxLispElement sub : curElement.getSubElements()) {
                initStateFromElement(sub, belongsTo);
            }
        }
        return state;
    }

    private void allocateDefIdToInputUnit () {
        inputSeq.forEach(input -> input.determineDefId(defIdMap));
    }

//    @JPerfMethod
    public List<List<MatchUnit>> match(List<MatchUnit> inputSeq) {
        this.inputSeq = inputSeq;
        allocateDefIdToInputUnit();
        Map<Integer, Set<DefID>> predicateMap
                = enablePredicateMap ? buildPredicateMatchMap(inputSeq, possibleFirstAcSet, pureContainsAcSet,
                                                              possibleEndSet)
                                     : null;
        genStarts (0, predicateMap);
        Optional<PureCursor> cursor;
        while (!cursorProvider.isEmpty()) {
            while ((cursor = cursorProvider.poll()).isPresent()) {
                PureCursor cursorBody = cursor.get();
                if (latestTryMatchCursor == null) {

                    latestTryMatchCursor = cursorBody;
                    latestTryMatchCursorList = CommonUtils.asWritableList(cursorBody);

                } else if (latestTryMatchCursor.getNextOffset() <= cursorBody.getNextOffset()) {
                    if (latestTryMatchCursor.getNextOffset() == cursorBody.getNextOffset()) {
                        latestTryMatchCursorList.add(cursorBody);
                    } else {
                        latestTryMatchCursor = cursorBody;
                        latestTryMatchCursorList = CommonUtils.asWritableList(cursorBody);
                    }
                }
                reduceOrExpandCursor(cursor.get(), predicateMap);
                // 每次 reduce 完毕检查下是否已经完全归约输入
                if (reachMatchEnd) {
                    break;
                }
            }
            if (reachMatchEnd) {
                break;
            }
            // 可归约的 cursor 为空时处理回滚 cursor，搜索重新归约的 cursor
            cursorProvider.consumeRollbackRefCursors()
                          .forEach(rollbackCursor -> {
                              rollbackReduceFailedCursor(rollbackCursor.getBelongsToDef(),
                                                         rollbackCursor.getDefStart(),
                                                         rollbackCursor.getRepeatStackLastNode(),
                                                         rollbackCursor.getId(),
                                                         predicateMap);
                          });
        }
        if (!reachMatchEnd) {
            throw new ParseException("匹配错误，最近匹配位置: " +
                                     latestTryMatchCursor.getCurOffset() +
                                     "," +
                                     latestTryMatchCursor.getNextOffset());
        }
        trimTrailMap();
        // 生成解析结果
        List<TrailUnit> trail = genResFromTrailMap(inputSeq.size());
        List<MatchUnit> outputSeq = trail.stream()
                                         .map(this::parseTrailUnitToMatchOutput)
                                         .collect(Collectors.toList());
        return Collections.singletonList(outputSeq);
    }

//    @JPerfMethod
    private void reduceOrExpandCursor(PureCursor cursor, Map<Integer, Set<DefID>> predicateMap) {

        if (cursor.isReducing()) {
            throw new ParseException("Reducing cursor can not be do with reduceOrExpandPvt!");
        }

        if (enablePrintReduceTrace) {
            System.out.println(cursor.toTrace());
        }

        reduceOrExpandCursor0(cursor.getBelongsToDef(), cursor.getNextOffset(), cursor.getDefStart(),
                              cursor.getCurMatchNode(),
                              cursor.getCurState(), cursor.getRepeatStackLastNode(), cursor.getId(),
                              false, predicateMap);
    }

    private void reduceOrExpandCursor0(DefID def,
                                       int nextOffset,
                                       int defStart,
                                       NewMatchSeqNode curSeqNode,
                                       MatchState curState,
                                       ListTreeNode<RepeatFrame, Boolean>  repeatNode,
                                       int srcCursorId,
                                       boolean isRollback,
                                       Map<Integer, Set<DefID>> predicateMap) {
        boolean hasMatchedNext = false;
        Boolean matchHunger = null;
        ListTreeNode<RepeatFrame, Boolean> curRepeatNode = repeatNode;
        // 在当前 Def body 内搜索所有可能的 cursor
        while (curState != null) {
            if (curState.isRepeat()) {
                RepeatFrame curRepeatFrame = curRepeatNode.getNodeKey();
                RepeatFrame copiedCurRepeatFrame;

                if (curRepeatFrame == null
                        || !curRepeatFrame.isSameRepeatState(curState)) {
                    copiedCurRepeatFrame = RepeatFrame.builder()
                                           .matchTime(0)
                                           .repeatState(curState)
                                           .build();
                } else {
                    copiedCurRepeatFrame = curRepeatFrame.copyForReduce();
                }

                if (copiedCurRepeatFrame.increase()) {
                    //
                    curRepeatNode = popRepeatStack(curRepeatNode);
                    // 往右走
                    Pair<Boolean, Boolean> goRightRes = goRight(curState, curRepeatNode, defStart, curSeqNode,
                                                                nextOffset, srcCursorId, isRollback, predicateMap);
                    matchHunger = getOrElseAnd(matchHunger, goRightRes.getSecond());
                    hasMatchedNext |= goRightRes.getFirst();
                } else {
                    copiedCurRepeatFrame.accessRepeatCurStart(nextOffset, curSeqNode);
                    curRepeatNode = pushRepeatStack(copiedCurRepeatFrame, curRepeatNode);

                    // match time 没有达到最大，则 match repeat body
                    List<MatchState.MatchPfRes> matchRepeatBodyResList
                            = curState.matchPfWithRes(inputSeq, nextOffset, predicateMap, enablePredicateMap);
                    if (!matchRepeatBodyResList.isEmpty()) {
                        hasMatchedNext = true;
                        // match repeat body result 加入 pvt，然后 break def body travel
                        for (MatchState.MatchPfRes matchRepeatBodyRes : matchRepeatBodyResList) {
                            Map<MatchState, Set<MatchState>> jumpTargetMap = matchRepeatBodyRes.getMatchMap();
                            expandCursors(jumpTargetMap, curRepeatNode, defStart, curSeqNode, nextOffset,
                                          matchRepeatBodyRes.getNextOffset(), srcCursorId, isRollback);
                        }
                        if (copiedCurRepeatFrame.isLongestMatchRepeat() || !copiedCurRepeatFrame.fit()) {
                            break;
                        } else {
                            // 当前 repeat 不是最长匹配模式，而且匹配次数已经达到可接受值
                            // 则直接收敛当前 repeat，然后 go right
                            curRepeatNode = popRepeatStack(curRepeatNode);
                            Pair<Boolean, Boolean> goRightRes = goRight(curState, curRepeatNode, defStart,
                                                                        curSeqNode, nextOffset, srcCursorId,
                                                                        isRollback, predicateMap);
                            matchHunger = getOrElseAnd(matchHunger, goRightRes.getSecond());
                        }
                    } else {
                        // 如果 match repeat body 失败，检查 match time 是否在可接受范围内
                        // 检查 match time 是否达到可接受范围，向右走
                        if (copiedCurRepeatFrame.fit()) {
                            curRepeatNode = popRepeatStack(curRepeatNode);
                            Pair<Boolean, Boolean> goRightRes = goRight(curState, curRepeatNode, defStart,
                                                                        curSeqNode, nextOffset, srcCursorId,
                                                                        isRollback, predicateMap);
                            matchHunger = getOrElseAnd(matchHunger, goRightRes.getSecond());
                            hasMatchedNext |= goRightRes.getFirst();
                        } else {
                            break;
                        }
                    }
                }
            } else {
                // 非 repeat，直接向右走
                Pair<Boolean, Boolean> goRightRes = goRight(curState, curRepeatNode, defStart, curSeqNode,
                                                            nextOffset, srcCursorId, isRollback, predicateMap);
                matchHunger = getOrElseAnd(matchHunger, goRightRes.getSecond());
                hasMatchedNext |= goRightRes.getFirst();
            }

            // 往上走（如果可以）
            if (!getOrElseFalse(matchHunger) && curState.isCanSkipToUpperNext()) {
                curState = curState.getUpper();
            } else {
                break;
            }
        }

        // 当前 Ref 收敛（如果可以）
        if (curState == null && !getOrElseFalse(matchHunger)) {
            reduceAsDef(def, defStart, nextOffset, curSeqNode, srcCursorId, isRollback, predicateMap);
        } else {
            // 如果没有匹配到任何 next，则 rollback
            if (!hasMatchedNext) {
                rollbackReduceFailedCursor(def, defStart, curRepeatNode, srcCursorId, predicateMap);
            }
        }
    }

    public ListTreeNode<RepeatFrame, Boolean> pushRepeatStack (RepeatFrame repeatFrame,
                                                               ListTreeNode<RepeatFrame, Boolean> curRepeatNode) {
        return curRepeatNode.isRoot()
               ? curRepeatNode.putNextLeafNode(repeatFrame, true)
               : curRepeatNode.getPrevNode().putNextLeafNode(repeatFrame, true);
    }

    public ListTreeNode<RepeatFrame, Boolean> popRepeatStack (ListTreeNode<RepeatFrame, Boolean> curRepeatNode) {
        return curRepeatNode.isRoot()
               ? curRepeatNode
               : curRepeatNode.getPrevNode();
    }

//    @JPerfMethod
    private void rollbackReduceFailedCursor (DefID def, int defStart,
                                             ListTreeNode<RepeatFrame, Boolean> curRepeatStackNode,
                                             int srcCursorId,
                                             Map<Integer, Set<DefID>> predicateMap) {

        if (curRepeatStackNode != null) {

            RepeatFrame topRepeatFrame = curRepeatStackNode.getNodeKey();

            if (topRepeatFrame != null && topRepeatFrame.fit()) {
                MatchState rollbackState = topRepeatFrame.getRepeatState();

                 // 先 goRight，然后 upper，然后复用 reduceOrExpandCursor
                NewMatchSeqNode curSeqNode = topRepeatFrame.getLatestPreMatchBodySeqNode();
                int nextOffset = topRepeatFrame.getEnterOffset();

                // 往右走
                Pair<Boolean, Boolean> goRightRes = goRight(rollbackState, curRepeatStackNode, defStart,
                                                            curSeqNode, nextOffset, srcCursorId, true, predicateMap);
                boolean matchHunger = goRightRes.getSecond();
                if (!matchHunger && rollbackState.isCanSkipToUpperNext()) {
                    rollbackState = rollbackState.getUpper();
                    reduceOrExpandCursor0(def, nextOffset, defStart, curSeqNode, rollbackState, curRepeatStackNode,
                                          srcCursorId, true, predicateMap);
                }
            }
        }
    }

    /**
     * 向右匹配 next，方法内会将匹配到的 next states 封装为新的 cursor 并放入 queue
     * @param curState 当前 match state
     * @param curRepeatStack repeat stack node
     * @param defStart cursor def start offset
     * @param prevSeqNode 上一个匹配结果 SeqNode
     * @param nextOffset 匹配开始位置
     * @return match res, first: has matched res, second: match hunger
     */
    private Pair<Boolean, Boolean> goRight(MatchState curState,
                                           ListTreeNode<RepeatFrame, Boolean> curRepeatStack,
                                           int defStart,
                                           NewMatchSeqNode prevSeqNode,
                                           int nextOffset,
                                           int srcCursorId,
                                           boolean isRollback,
                                           Map<Integer, Set<DefID>> predicateMap) {

        LambdaBoolean matchHunger = new LambdaBoolean(true);
        List<MatchState.MatchPfRes> matchResList
                = curState.matchNextPfWithRes(inputSeq, nextOffset, predicateMap, enablePredicateMap);
        matchResList.forEach(matchRes -> {
            Map<MatchState, Set<MatchState>> jumpTargetMap = matchRes.getMatchMap();

            expandCursors(jumpTargetMap, curRepeatStack, defStart, prevSeqNode, nextOffset, matchRes.getNextOffset(),
                          srcCursorId, isRollback);
            // matchHunger 设定为 所有匹配结果都为 Hunger Match 才为 true
            if (matchHunger.get()) {
                matchHunger.set(jumpTargetMap.keySet()
                                             .stream()
                                             .anyMatch(baseState -> curState.getHungerStateSet()
                                                                            .contains(baseState)));
            }
        });
        return Pair.<Boolean, Boolean>builder()
                         .first(!CollectionUtils.isEmpty(matchResList))
                         .second(!CollectionUtils.isEmpty(matchResList) && matchHunger.get())
                         .build();
    }

    private void reduceAsDef (DefID reducedDef, int reducedDefStart, int reducedDefEnd, NewMatchSeqNode curSeqNode,
                              int srcCursorId, boolean isRollback, Map<Integer, Set<DefID>> predicateMap) {

        // 第 0 步：将当前 def 收敛结果存至 def 匹配结果表
        NewMatchSeqNode reducedDefNode = NewMatchSeqNode.builder()
                                                    .def(reducedDef.getDef())
                                                    .type(NewMatchSeqNode.SeqNodeType.DEF)
                                                    .start(reducedDefStart)
                                                    .end(reducedDefEnd)
                                                    .subLastSeqNode(curSeqNode)
                                                    .build();
        defMatchResMap.computeIfAbsent(reducedDef, def -> new HashMap<>())
                      .computeIfAbsent(reducedDefStart, start -> new HashMap<>())
                      .computeIfAbsent(reducedDefEnd, end -> reducedDefNode);

        // 第一步：看当前收敛的 def 是否为 entry，是则作为 entry 收敛至 trailMap
        if (entryMap.containsKey(reducedDef)) {
            TrailUnit curTrail = genDefMatchSeqNode(reducedDef, reducedDefStart, reducedDefEnd, curSeqNode);
            addTrail(curTrail);
            if (curTrail.getEnd() >= inputSeq.size()) {
                reachMatchEnd = true;
            } else {
                genStarts(curTrail.getEnd(), predicateMap);
            }
        }

        if (reachMatchEnd) {
            return;
        }

        // 第二步：检查所有具有相同 startOffset 的 ref pvt，收敛到这些 ref pvt
        List<PureCursor> reducingRefCursorSet = cursorProvider.getRefCursorSet(reducedDefStart, reducedDef);
        // 将 ref cursor 从 candidate ref cursor 中去除
        cursorProvider.removeRollbackCandidateRefCursorList(reducedDefStart, reducedDef);
        for (PureCursor reducingRefCursor : reducingRefCursorSet) {
            NewMatchSeqNode reducedSeqNode = genReducedRefSeqNodeFromCursor(reducingRefCursor.getCurState(),
                                                                            reducedDefStart, reducedDefEnd, curSeqNode);
            reducedSeqNode.setMatchState(reducingRefCursor.getCurState());
            // 加入到当前队列中
            putReducedRefCursor (reducingRefCursor, reducedSeqNode, srcCursorId, isRollback);
        }

        // 第三步：找到所有可收敛（但没有对应的 ref pvt）def，找到其对应的 ref frame，并 putStartPvt
        Set<DefID> reduceToDefSet = directReduceToFirstRefMap.getOrDefault(reducedDef, Collections.emptySet());
        Map<DefID, List<PureCursor>> sameStartPvtMap = cursorProvider.getRefCursorMap(reducedDefStart);
        if (!CollectionUtils.sizeIsEmpty(sameStartPvtMap)) {

            Set<DefID> canReduceToDefSet = new HashSet<>();

            for (DefID reduceToDef : reduceToDefSet) {
                // 收敛到所有能作为 head ref 收敛到目前需要收敛的具有相同 startOffset 的 ref pvt 中
                sameStartPvtMap.keySet()
                               .forEach(curRefPvtRef -> {
                                   if (curRefPvtRef.equals(reduceToDef)) {
                                       canReduceToDefSet.add(reduceToDef);
                                   } else {
                                       Set<DefID> firstRefReduceSet = firstRefReduceMap.get(curRefPvtRef);
                                       if (firstRefReduceSet.contains(reduceToDef)) {
                                           canReduceToDefSet.add(reduceToDef);
                                       }
                                   }
                               });
            }

            canReduceToDefSet
                    .forEach(targetDef -> putRefStartCursor(targetDef, reducedDef, reducedDefStart, reducedDefEnd,
                                                            curSeqNode, srcCursorId, isRollback));
        }
    }

    private NewMatchSeqNode genReducedRefSeqNodeFromCursor(MatchState refState, int defStart, int nextOffset,
                                                           NewMatchSeqNode subLastSeqNode) {
        return NewMatchSeqNode.builder()
                              .type(NewMatchSeqNode.SeqNodeType.DEF)
                              .def(refState.getRefName())
                              .start(defStart)
                              .end(nextOffset)
                              .matchState(refState)
                              .subLastSeqNode(subLastSeqNode)
                              .build();
    }

    private void expandCursors(Map<MatchState, Set<MatchState>> matchedJumpTargetMap,
                               ListTreeNode<RepeatFrame, Boolean> lastCursorRepeatStack,
                               int defStart,
                               NewMatchSeqNode lastSeqNode,
                               int curOffset,
                               int nextOffset,
                               int srcCursorId,
                               boolean isRollback) {

        matchedJumpTargetMap.forEach((baseTarget, directTargetSet) -> {

            boolean matchBaseDirect = directTargetSet.stream()
                                                     .anyMatch(directTarget -> !directTarget.isRef());
            Set<MatchState> refDirectSet = directTargetSet.stream()
                                                          .filter(MatchState::isRef)
                                                          .collect(Collectors.toSet());

            if (matchBaseDirect) {
                putBodyCursor(baseTarget, curOffset, nextOffset,  lastCursorRepeatStack, defStart, lastSeqNode,
                              srcCursorId, isRollback);
            }

            if (!CollectionUtils.isEmpty(refDirectSet)) {

                for (MatchState refDirectState : refDirectSet) {

                    // 直接规约（一级）
                    checkRefDirectStateAndReducedIfMatched(refDirectState, curOffset, lastCursorRepeatStack, defStart,
                                                           lastSeqNode, srcCursorId, isRollback);
                    // 间接规约（二级）
                    DefID startRef = refDirectState.getDefID();
                    DefID endDef = baseTarget.getBelongsToDef();
                    Set<DefID> midDefSet = firstRefReduceMidSetMap.getOrDefault(startRef, Collections.emptyMap())
                                                                  .getOrDefault(endDef, Collections.emptySet());
                    Set<DefID> canReduceToSet =  firstRefReduceMap.getOrDefault(startRef, Collections.emptySet());
                    midDefSet.forEach(midDef -> {
                        reduceAsFirstRefStatesMap
                                .getOrDefault(midDef, Collections.emptyMap())
                                .forEach((midRefAsFirstRef, refSet) -> {
                                    if (canReduceToSet.contains(midRefAsFirstRef)
                                            || midRefAsFirstRef.equals(startRef)) {
                                        refSet.forEach(targetRef -> {
                                            checkRefDirectStateAndReducedIfMatched(targetRef, curOffset,
                                                                                   lastCursorRepeatStack, defStart,
                                                                                   null, srcCursorId, isRollback);
                                        });
                                    }
                                });
                    });

                    putBodyCursor(refDirectState, curOffset, Constant.REDUCING_NEXT_OFFSET, lastCursorRepeatStack,
                                  defStart, lastSeqNode, srcCursorId, isRollback);
                }

                putEmptyStartCursor(baseTarget, curOffset, nextOffset, srcCursorId, isRollback);
            }
        });
    }

    private void checkRefDirectStateAndReducedIfMatched (MatchState refDirectState,
                                                         int curOffset,
                                                         ListTreeNode<RepeatFrame, Boolean> lastCursorRepeatStack,
                                                         int defStart,
                                                         NewMatchSeqNode lastSeqNode,
                                                         int srcCursorId,
                                                         boolean isRollback) {
        Collection<NewMatchSeqNode> matchedResSet
                = defMatchResMap.getOrDefault(refDirectState.getDefID(), Collections.emptyMap())
                                .getOrDefault(curOffset, Collections.emptyMap())
                                .values();
        if (!CollectionUtils.isEmpty(matchedResSet)) {
            if (lastSeqNode != null) {
                for (NewMatchSeqNode matchedRes : matchedResSet) {
                    putHistoryMatchedRefCursor(refDirectState, matchedRes, lastCursorRepeatStack, defStart, lastSeqNode,
                                               srcCursorId, isRollback);
                }
            } else {
                for (NewMatchSeqNode matchedRes : matchedResSet) {
                    putEmptyStartCursor(refDirectState, curOffset, matchedRes.getEnd(), srcCursorId, isRollback);
                }
            }
        }
    }

    private void genStarts (int offset, Map<Integer, Set<DefID>> predicateMap) {
        entryMap.forEach((def, entryState) -> {

            List<MatchState.MatchPfRes> matchPfResList
                    = entryState.matchPfWithRes(inputSeq, offset, predicateMap, enablePredicateMap);
            for (MatchState.MatchPfRes matchPfRes : matchPfResList) {

                int nextOffset = matchPfRes.getNextOffset();

                matchPfRes.getMatchMap().forEach((baseTargetState, directTargetStateSet) -> {

                    putEmptyStartCursor(baseTargetState, offset, nextOffset, Constant.NO_SRC_CURSOR_ID, false);

                    directTargetStateSet.forEach(directTargetState -> {

                        if (directTargetState.isRef()) {
                            putEmptyStartCursor(directTargetState, offset, Constant.REDUCING_NEXT_OFFSET,
                                                Constant.NO_SRC_CURSOR_ID,
                                                false);
                        }
                    });
                });
            }
        });
    }

    private void putRefStartCursor(DefID reduceToDef, DefID def, int defStart, int nextOffset,
                                   NewMatchSeqNode matchSeqNode, int srcCursorId, boolean isRollback) {

        defDirectRefPfStatesMap.get(reduceToDef)
                               .getOrDefault(def, Collections.emptySet())
                               .forEach(firstRefState -> {
                                   NewMatchSeqNode curNode = genReducedRefSeqNodeFromCursor(firstRefState, defStart,
                                                                                            nextOffset, matchSeqNode);
                                   curNode.setMatchState(firstRefState);

                                   PureCursor.ComeFromInfo comeFromInfo
                                           = PureCursor.ComeFromInfo.builder()
                                                                    .comeFromCursorId(srcCursorId)
                                                                    .comeFromType(determineComeFromType(isRollback, true))
                                                                    .build();
                                   PureCursor startCursor = PureCursor.builder()
                                                                      .id(cursorIdGenerator.getAndIncrease())
                                                                      .curState(firstRefState)
                                                                      .defStart(curNode.getStart())
                                                                      .curOffset(curNode.getStart())
                                                                      .nextOffset(curNode.getEnd())
                                                                      .curMatchNode(curNode)
                                                                      .repeatStackLastNode(repeatFrameListTree.getRoot())
                                                                      .comeFromInfo(comeFromInfo)
                                                                      .build();
                                   cursorProvider.offer(startCursor);
                               });
    }

    private PureCursor.ComeFromType determineComeFromType (boolean rollback, boolean isReduce) {
        if (rollback && isReduce) {
            return PureCursor.ComeFromType.ROLLBACK_REF_REDUCE;
        } else if (rollback && !isReduce) {
            return PureCursor.ComeFromType.ROLLBACK_EXPAND;
        } else if (!rollback && isReduce) {
            return PureCursor.ComeFromType.REF_REDUCE;
        } else {
            return PureCursor.ComeFromType.EXPAND;
        }
    }

//    @JPerfMethod
    private void putEmptyStartCursor(MatchState targetState, int curOffset, int nextOffset, int srcCursorId,
                                     boolean isRollback) {
        PureCursor.ComeFromInfo comeFromInfo
                = PureCursor.ComeFromInfo.builder()
                                         .comeFromCursorId(srcCursorId)
                                         .comeFromType(srcCursorId == Constant.NO_SRC_CURSOR_ID
                                                       ? PureCursor.ComeFromType.GEN_START
                                                       : determineComeFromType(isRollback, false))
                                         .build();
        PureCursor startCursor = PureCursor.builder()
                                           .id(cursorIdGenerator.getAndIncrease())
                                           .repeatStackLastNode(repeatFrameListTree.getRoot())
                                           .curState(targetState)
                                           .defStart(curOffset)
                                           .curOffset(curOffset)
                                           .nextOffset(nextOffset)
                                           .comeFromInfo(comeFromInfo)
                                           .build();
        if (cursorProvider.offer(startCursor)) {
            startCursor.setCurMatchNode(genMatchSeqNode(targetState, curOffset, nextOffset));
        }
    }

//    @JPerfMethod
    private void putBodyCursor(MatchState targetState, int curOffset, int nextOffset,
                               ListTreeNode<RepeatFrame, Boolean> lastCursorRepeatStack,
                               int defStart,
                               NewMatchSeqNode lastSeqNode,
                               int srcCursorId,
                               boolean isRollback) {

        PureCursor.ComeFromInfo comeFromInfo
                = PureCursor.ComeFromInfo.builder()
                                         .comeFromCursorId(srcCursorId)
                                         .comeFromType(srcCursorId == Constant.NO_SRC_CURSOR_ID
                                                       ? PureCursor.ComeFromType.GEN_START
                                                       : determineComeFromType(isRollback, false))
                                         .build();
        PureCursor bodyCursor = PureCursor.builder()
                                          .id(cursorIdGenerator.getAndIncrease())
                                          .curState(targetState)
                                          .repeatStackLastNode(lastCursorRepeatStack)
                                          .defStart(defStart)
                                          .curOffset(curOffset)
                                          .nextOffset(nextOffset)
                                          .comeFromInfo(comeFromInfo)
                                          .build();

        if (cursorProvider.offer(bodyCursor)) {
            NewMatchSeqNode curSeqNode = genMatchSeqNode(targetState, curOffset, nextOffset);
            bodyCursor.setCurMatchNode(curSeqNode);
            bindMatchSeqNode(lastSeqNode, curSeqNode);
        }
    }

//    @JPerfMethod
    private void putHistoryMatchedRefCursor(MatchState targetState,
                                            NewMatchSeqNode matchedRefNode,
                                            ListTreeNode<RepeatFrame, Boolean> lastCursorRepeatStack,
                                            int defStart,
                                            NewMatchSeqNode lastSeqNode,
                                            int srcCursorId,
                                            boolean isRollback) {

        PureCursor.ComeFromInfo comeFromInfo
                = PureCursor.ComeFromInfo.builder()
                                         .comeFromCursorId(srcCursorId)
                                         .comeFromType(srcCursorId == Constant.NO_SRC_CURSOR_ID
                                                       ? PureCursor.ComeFromType.GEN_START
                                                       : determineComeFromType(isRollback, false))
                                         .build();
        NewMatchSeqNode curRefNode = genReducedRefSeqNodeFromCursor(targetState,
                                                                    matchedRefNode.getStart(),
                                                                    matchedRefNode.getEnd(),
                                                                    matchedRefNode.getSubLastSeqNode());
        PureCursor matchedRefCursor = PureCursor.builder()
                                                .id(cursorIdGenerator.getAndIncrease())
                                                .curState(targetState)
                                                .repeatStackLastNode(lastCursorRepeatStack)
                                                .defStart(defStart)
                                                .curOffset(matchedRefNode.getStart())
                                                .nextOffset(matchedRefNode.getEnd())
                                                .curMatchNode(curRefNode)
                                                .comeFromInfo(comeFromInfo)
                                                .build();

        if (cursorProvider.offer(matchedRefCursor)) {
            bindMatchSeqNode(lastSeqNode, curRefNode);
        }
    }


//    @JPerfMethod
    private void putReducedRefCursor(PureCursor originalRefCursor,
                                     NewMatchSeqNode reducedSeqNode,
                                     int srcCursorId,
                                     boolean isRollback) {

        PureCursor.ComeFromInfo comeFromInfo
                = PureCursor.ComeFromInfo.builder()
                                         .comeFromCursorId(srcCursorId)
                                         .comeFromType(srcCursorId == Constant.NO_SRC_CURSOR_ID
                                                       ? PureCursor.ComeFromType.GEN_START
                                                       : determineComeFromType(isRollback, true))
                                         .build();
        PureCursor startCursor = PureCursor.builder()
                                           .id(cursorIdGenerator.getAndIncrease())
                                           .curState(originalRefCursor.getCurState())
                                           .defStart(originalRefCursor.getDefStart())
                                           .curOffset(originalRefCursor.getCurOffset())
                                           .nextOffset(reducedSeqNode.getEnd())
                                           .curMatchNode(reducedSeqNode)
                                           .repeatStackLastNode(originalRefCursor.getRepeatStackLastNode())
                                           .comeFromInfo(comeFromInfo)
                                           .build();

        if (cursorProvider.offer(startCursor)) {
            // 将 originalRefCursor 的 MatchSeqNode uppers 与 reducedSeqNode 绑定
            transBindingUppers(originalRefCursor.getCurMatchNode(), reducedSeqNode);
        }
    }

    private NewMatchSeqNode genMatchSeqNode (MatchState targetState, int curOffset, int nextOffset) {
        return NewMatchSeqNode.builder()
                              .type(targetState.isRef()
                                    ? NewMatchSeqNode.SeqNodeType.DEF
                                    : NewMatchSeqNode.SeqNodeType.BASE)
                              .start(curOffset)
                              .end(nextOffset)
                              .def(targetState.getRefName())
                              .matchState(targetState)
                              .build();
    }

    private void transBindingUppers (NewMatchSeqNode original, NewMatchSeqNode cur) {
        if (!CollectionUtils.isEmpty(original.getPrevSet())) {
            original.getPrevSet().forEach(upper -> bindMatchSeqNode(upper, cur));
        }
    }

    private void bindMatchSeqNode(NewMatchSeqNode last, NewMatchSeqNode next) {
        if (last.isReducing()) {
            throw new ParseException("Reducing MatchSeqNode can not be bounded as the last node!");
        }
        boolean successBind;
        boolean addUpper = next.addUpper(last);
        if (next.isReducing()) {
            boolean addReducing = last.addReducingNetSet(next);
            successBind = (addUpper && addReducing) || (!addUpper && !addReducing);
        } else {
            boolean addNext = last.addNext(next);
            successBind = (addUpper && addNext) || (!addUpper && !addNext);
        }
        if (!successBind) {
            throw new ParseException("add next 与 add upper 结果不一致！");
        }
    }

    private List<TrailUnit> genResFromTrailMap (int stopOffset) {
        List<TrailUnit> trails = new ArrayList<>();
        int next = 0;
        while (next < stopOffset) {
            Map<Integer, List<TrailUnit>> endTrailMap = trailMap.get(next);
            try {
                Map.Entry<Integer, List<TrailUnit>> firstEntry = endTrailMap.entrySet().iterator().next();
                trails.add(firstEntry.getValue().get(0));
                next = firstEntry.getKey();
            } catch (NullPointerException e) {
                e.printStackTrace();
                break;
            }
        }
        return trails;
    }

    private void trimTrailMap () {
        Queue<TrailUnit> queue = new ArrayDeque<>();
        Set<Integer> visitedStart = new HashSet<>();
        trailMap.get(0)
                .forEach((e, startTrails) -> queue.addAll(startTrails));
        visitedStart.add(0);
        while (!queue.isEmpty()) {
            TrailUnit curTrail = queue.poll();
            int nextStart = curTrail.getEnd();
            if (!visitedStart.contains(nextStart)) {
                if (nextStart < inputSeq.size()) {
                    if (trailMap.containsKey(nextStart)) {
                        trailMap.get(nextStart)
                                .forEach((e, trails) -> queue.addAll(trails));
                    } else {
                        removeTrail(curTrail);
                    }
                }
                visitedStart.add(nextStart);
            }
        }
    }

    private void removeTrail (TrailUnit trailUnit) {
        int start = trailUnit.getStart();
        int end = trailUnit.getEnd();
        List<TrailUnit> trailUnitList = trailMap.get(start)
                                                .get(end);
        trailUnitList.remove(trailUnit);
        if (trailUnitList.isEmpty()) {
            Map<Integer, List<TrailUnit>> endTrailMap = trailMap.get(start);
            endTrailMap.remove(end);
            if (endTrailMap.isEmpty()) {
                trailMap.remove(start);
                removeTrail(start);
            }
        }
    }

    private TrailUnit genDefMatchSeqNode (DefID def, int start, int end, NewMatchSeqNode curSeqNode) {
        return new TrailUnit(start, end, def.getDef(), curSeqNode);
    }

    private void addTrail (TrailUnit curTrail) {
        trailMap.computeIfAbsent(curTrail.getStart(), start -> new HashMap<>())
                .computeIfAbsent(curTrail.getEnd(), end -> new ArrayList<>())
                .add(curTrail);
        // trail 加入 endMap
        trailWithEndMap.computeIfAbsent(curTrail.getEnd(), end -> new HashSet<>())
                       .add(curTrail.getStart());
    }

    /**
     * 移除所有以 removeEnd 为收尾的 trail link
     * @param removeEnd
     */
    private void removeTrail (int removeEnd) {
        Set<Integer> curRemoveSet = new HashSet<>();
        curRemoveSet.add(removeEnd);
        while (!curRemoveSet.isEmpty()) {
            Set<Integer> nextRemoveSet = new HashSet<>();
            for (Integer curEnd : curRemoveSet) {
                Set<Integer> endTrailUnits = trailWithEndMap.remove(curEnd);
                if (endTrailUnits != null) {
                    for (Integer start : endTrailUnits) {
                        Map<Integer, List<TrailUnit>> startMap = trailMap.get(start);
                        startMap.remove(curEnd);
                        if (startMap.isEmpty()) {
                            trailMap.remove(start);
                            nextRemoveSet.add(start);
                        }
                    }
                }
            }
            curRemoveSet = nextRemoveSet;
        }
    }

    MatchUnit parseTrailUnitToMatchOutput (TrailUnit c) {
        MatchUnit MatchUnit = org.syntaxlisp.core.match.MatchUnit.builder()
                                                                 .name(c.getDef())
                                                                 .type(MatchUnitType.BASE)
                                                                 .build();
        List<MatchUnit> subs = parseLevelSubs(c.getLastNode());
        MatchUnit.setSubs(subs);
        MatchUnit.genSourcePositionScope();
        return MatchUnit;
    }

    List<MatchUnit> parseLevelSubs (NewMatchSeqNode lastNode) {
        List<MatchUnit> subs = new ArrayList<>();
        NewMatchSeqNode subSeqNode = lastNode;
        while (subSeqNode != null) {
            subs.add(parseSingleMatchSeqNodeToMatchOutput(subSeqNode));
            if (!CollectionUtils.isEmpty(subSeqNode.getPrevSet())) {
                subSeqNode = subSeqNode.getPrevSet()
                                       .stream()
                                       .findFirst()
                                       .get();
            } else {
                break;
            }
        }
        Collections.reverse(subs);
        return subs;
    }

    MatchUnit parseSingleMatchSeqNodeToMatchOutput(NewMatchSeqNode matchSeqNode) {
        MatchUnit res = MatchUnit.builder().build();
        if (NewMatchSeqNode.SeqNodeType.DEF == matchSeqNode.getType()) {
            // REF 处理
            String def = matchSeqNode.getMatchState() != null
                            && SyntaxLispElementType.REF.isTypeMatch(matchSeqNode.getMatchState().getSrc())
                         ? matchSeqNode.getMatchState().getRefName()
                         : matchSeqNode.getDef();
            res.setType(MatchUnitType.BASE);
            res.setName(def);
            List<MatchUnit> subs = parseLevelSubs(matchSeqNode.getSubLastSeqNode());
            res.setSubs(subs);
            if (CollectionUtils.isEmpty(subs)) {
                res.setSrcPositionScope(PositionScope.builder()
                                                     .startPosition(matchSeqNode.getStart())
                                                     .endPosition(matchSeqNode.getEnd())
                                                     .build());
            } else {
                res.genSourcePositionScope();
            }
        } else {
            // NewMatchSeqNode.SeqNodeType.BASE == matchSeqNode.getType()
            if (MatchUnitType.BASE == inputSeq.get(matchSeqNode.getStart()).getType()) {
                MatchUnit curInput = inputSeq.get(matchSeqNode.getStart());
                res.setType(MatchUnitType.BASE);
                res.setVal(curInput.getVal());
                res.setName(curInput.getName());
                res.setSubs(curInput.getSubs());
                res.setSrcPositionScope(curInput.getSrcPositionScope());
            } else {
                StringBuilder valBuilder = new StringBuilder();
                List<PositionScope> srcPositionScopes
                        = new ArrayList<>(matchSeqNode.getEnd() - matchSeqNode.getStart());
                for (int i = matchSeqNode.getStart(); i < matchSeqNode.getEnd(); i++) {
                    valBuilder.append(inputSeq.get(i).getVal());
                    srcPositionScopes.add(inputSeq.get(i).getSrcPositionScope());
                }
                res.setType(MatchUnitType.STRING);
                res.setVal(valBuilder.toString());
                res.genSourcePositionScope(srcPositionScopes);
            }
        }
        return res;
    }
}
